#include "define.h"
Status InitSString(SString *&s){
    s = (SString *)malloc(sizeof(SString));
    if(!s) return FAIL;
    s->length = 0;
    return SUCCESS;
}
Status CreateSString(SString *&s, Elemtype a[], int n){
    s = (SString *)malloc(sizeof(SString));
    if(!s) return FAIL;
    for(int i=0; i<n; i++)s->data[i] = a[i];
    s->length = n;
}
void destroySString(SString *&s){
    free(s);
}
void DisplaySString(SString *s){
    if(!s->length) return;
    for(int i=0;i<s->length;i++) cout << s->data[i];
    cout << endl;
}
//B-F
int index(SString *S, SString *T){
    int i=0, j=0;
    while(i<S->length&&j<T->length){
        if(S->data[i]==T->data[j]){
            ++i;++j;
        }
        else{
            i = i-j+1; j = 0;
        }
    }
    if(j>=T->length) return i-T->length;
    else return -1;
}
//KMP
void GetNext(SString *T, int next[]){
    int k = -1; int j = 0;
    next[0] = -1;
    while(j<T->length-1){
        if(k==-1 || T->data[k]==T->data[j]){
            ++k; ++j;
            next[j] = k;
        }
        else{
            k = next[k];
        }
    }
}
int KMPIndex(SString *S, SString *T){
    int i, j = 0;
    int Next[T->length];
    GetNext(T, Next);
    while(i<S->length&&j<T->length){
        if(j==-1||T->data[j]==S->data[i]){
            ++j; ++i;
        }
        else j = Next[j];
    }
    if(j>=T->length) return i-T->length;
    else return -1;
}
